/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Feb 28, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a collection of numbers, return all possible permutations.
 * 
 *              For example, [1,2,3] have the following permutations: [1,2,3],
 *              [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
 */
public class Permutations {

	public ArrayList<ArrayList<Integer>> res;
	public ArrayList<Integer> list;

	public ArrayList<ArrayList<Integer>> permute(int[] num) {
		res = new ArrayList<ArrayList<Integer>>();
		list = new ArrayList<Integer>();
		perm(num, 0);
		
		return res;
	}

	// nice job!
	private void perm(int[] num, int cur) {
		if (cur == num.length) {
			for (int i = 0; i < num.length; i++)
				list.add(num[i]);
			res.add(list);
			list = new ArrayList<Integer>();
		}
		
		for (int i = cur; i < num.length; i++) {
			swap(num, i, cur);
			perm(num, cur + 1);
			swap(num, i, cur);
		}
	}
	
	private void swap(int[] num, int i, int j) {
		int temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}

	@Test
	public void test() {
		System.out.println(permute(new int[]{1, 2, 3, 4}));
	}
}
